package nachos.vm;

import java.io.IOException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Random;

import nachos.machine.*;
import nachos.threads.*;
import nachos.userprog.*;

/**
 * A kernel that can support multiple demand-paging user processes.
 */
public class VMKernel extends UserKernel {
    private static Semaphore lmutex;
	/**
     * Allocate a new VM kernel.
     */
    public VMKernel() {
	super();
    }

    /**
     * Initialize this kernel.
     */
    public void initialize(String[] args) {
	super.initialize(args);
        //group 7 - initalize variables
   	tmutex = new Semaphore(1);
   	lmutex = new Semaphore(1);
	pagePin = new Semaphore(1);
	invPageTable = new HashMap<String,TranslationEntry>();
	swapPin = new Semaphore(1);
	swapFile = this.fileSystem.open(swapFileName, true);
	pinnedPages = new HashMap<String, Integer>();
	pagesInSwap = new HashMap<String, Integer>();
	pagesInUse = new HashMap<String, TranslationEntry>();
	freePagesInSwap = new SynchList();
	
	clockHand = 0;//for Clock algorithim
    }

    /**
     * Test this kernel.
     */	
    public void selfTest() {
	super.selfTest();
    }

    /**
     * Start running user programs.
     */
    public void run() {
	super.run();
    }
    
    /**
     * Terminate this kernel. Never returns.
     */
    public void terminate() {
    	Lib.debug(dbgVM, "VMKERNEL TERMINATING!!!!!");
    	swapFile.close();
    	this.fileSystem.remove(swapFileName);
    	Lib.debug(dbgVM, "calling super to terminate");
	super.terminate();
    }

    //group 7     
    public static TranslationEntry getPageFromMemory(int pid, int vpn){
    	String key = createKey(pid, vpn);
    	return getPageFromMemory(key);
    	
    }
    
    public static TranslationEntry getPageFromMemory(String key){
    	TranslationEntry retVal;
    	tmutex.P();
    	retVal = invPageTable.get(key);
    	tmutex.V();
    	return retVal;
    }
    
    public static TranslationEntry getPageFromExisting(int pid, int vpn){
    	String key = createKey(pid, vpn);
    	return pagesInUse.get(key);
    	
    }

    public static void addPageToMemory(String key, TranslationEntry te){
    	tmutex.P();
    	Lib.debug(dbgVM, "Adding page to memory: " + key);
    	invPageTable.put(key, te);
    	tmutex.V();
    }
    
    // a procedure to mark the page "in use" so it cannot be evicted from memory.
    // it just adds the page to the map of pages in use
    public static void pinPage(int pid, int vpn){
    	pagePin.P();
    	pinnedPages.put(createKey(pid,vpn), vpn);
    	pagePin.V();
    }
    
    // a procedure to unpin the page, it removes the page from the map of pages in use. 
    public static void unpinPage(int pid, int vpn){
    	pagePin.P();
    	pinnedPages.remove(createKey(pid,vpn));
    	pagePin.V();
    }
    
   public static boolean pageExistsForProcess(int pid, int vpn){
    	boolean retVal = false;
    	pagePin.P();
    	if(pinnedPages.containsKey(createKey(pid, vpn)));
    		retVal = true;
    	pagePin.V();
    	return retVal;
    }
    
    //functions that swaps the page out:
    public static void swapPageOut() throws IOException{
    	int offset = 0;
    	tmutex.P();
    	String key = findPageToEvict();
    	int ppn = invPageTable.get(key).ppn;
    	Lib.debug(dbgVM, "evicting page: " + key + " with ppn: " + ppn);
    	if(invPageTable.get(key).dirty){
    		swapPin.P();
        	Lib.debug(dbgVM, "Writing page to swap, swap file length is: " + swapFile.length());
        	if(freePagesInSwap.size() > 0){
        		offset = (Integer) freePagesInSwap.removeFirst();
        	}else{
        		if(swapFile.length() > 0)
        			offset = swapFile.length();
        	}
        	Lib.debug(dbgVM, "offset to write the page to is: " + offset);
        	int pageAddress = getMemoryPageAddress(getPidfromKey(key), getVPNfromKey(key));
        	Lib.debug(dbgVM, "Swapping out page at address: " + pageAddress);
    	   	int bytesWritten = swapFile.write(Machine.processor().getMemory(), pageAddress , Machine.processor().pageSize);
    	   	if(bytesWritten < Machine.processor().pageSize){
        		//did not get a full page, throw exception
        		swapPin.V();
        		tmutex.V();
        		throw new IOException();
        	}
    	   	pagesInSwap.put(key, offset);
    	   	swapPin.V();
    	}
    	invPageTable.remove(key);
    	returnPage(ppn);
    	tmutex.V();
    }
       
    //function that swaps the page in:
    public static void swapPageIn(int pid, int vpn) throws IOException{
    	String key = createKey(pid, vpn);
    	tmutex.P();
    	swapPin.P();
    	//find the right section of the swap file first
    	int offset = pagesInSwap.get(key);
    	//now find the physical page where we are going to load this
    	
    	int ppn = getFreePage();
    	byte[] memory = Machine.processor().getMemory();
    	int pageAddress = Machine.processor().makeAddress(ppn, 0);
    	TranslationEntry te = new TranslationEntry(vpn,ppn, true,false,false,false);
    	//add the page to the pageTable:
    	invPageTable.put(key, te);
    	int bytesRead = swapFile.read(offset, memory, pageAddress, Machine.processor().pageSize);
    	if(bytesRead < Machine.processor().pageSize){
    		//did not get a full page, throw exception
    		swapPin.V();
    		tmutex.V();
    		throw new IOException();
    	}
    	//now free up the swap file space:
    	freePagesInSwap.add(offset);
    	//and remove the page from the list of pages in swap:
    	pagesInSwap.remove(key);
    	swapPin.V();
    	tmutex.V();
    }
    
    public static boolean isInMemory(int pid, int vpn){
    	boolean retVal = false;
    	String key = createKey(pid, vpn);
    	tmutex.P();
    	if(invPageTable.containsKey(key)){
    		retVal = true;
    	}
    	tmutex.V();
    	return retVal;
    }
    
    //functions that check is page is in swap:
    public static boolean isPageInSwap(int pid, int vpn){
    	boolean retVal = false;
    	swapPin.P();
    	if(pagesInSwap.containsKey(pid+":"+vpn))
    		retVal = true;
    	swapPin.V();
    	return retVal;
    	
    }
    
    //routine to create inverted table key
    public static String createKey(int pid, int vpn){
    	StringBuffer key = new StringBuffer();
    	key.append(pid);
    	key.append(keySeparator);
    	key.append(vpn);
    	return key.toString();
    }
    
    // routine to get the pid from the table key:
    public static int getPidfromKey(String key){
    	int sepIndex = key.indexOf(keySeparator);
    	int pid = Integer.parseInt(key.substring(0, sepIndex));
    	return pid;
    	
    }
    
    //routine to get the vpn from the table key:
    public static int getVPNfromKey(String key){
    	int sepIndex = key.indexOf(keySeparator);
    	int vpn = Integer.parseInt(key.substring(sepIndex+1));
    	return vpn;
    }
   //routine to get the physical page address
   public static int getMemoryPageAddress(int pid, int vpn){
	   String key = createKey(pid, vpn);
	   int  ppn = invPageTable.get(key).ppn;
	   int address = Processor.makeAddress(ppn, 0);
	   return address; 
   }
   
   
   //finds the page to evict from memory:
   private static String findPageToEvict(){
	   //return findPageToEvictRandom();
	   return findPageToEvictClock();
   }
   
   private static String findPageToEvictRandom(){
	   Random r = new Random();
	   Iterator <String> clockItr;
	   String key;
	   TranslationEntry te;
	   
	   while(true){
		   clockItr = invPageTable.keySet().iterator();
		   for(int i = 0; i < r.nextInt(invPageTable.size()) - 1; i++)
			   clockItr.next();
	   
		   key = (String)clockItr.next();
		   //te = invPageTable.get(key);

		   if(pinnedPages.containsKey(key) || invPageTable.get(key).dirty)
			   continue;
		   
		   if(!invPageTable.get(key).used && !invPageTable.get(key).dirty)
			   return key;
	   }
   }
   
   private static String findPageToEvictClock(){
	   Iterator <String> clockItr = invPageTable.keySet().iterator();
	   //TranslationEntry te;
	   String key = "";
	   boolean found = false;
	   
	   //Move iterator to correct clockhand position
	   for(int i = 0; i < clockHand; i++)
		   clockItr.next();
	   
	   while(clockItr.hasNext() && !found){
			   key = (String)clockItr.next();
			  // te = invPageTable.get(key);			
			   clockHand++;  
			   if(pinnedPages.containsKey(key) || invPageTable.get(key).dirty)
				   continue;
			   		
			   //Return page if it hasn't been used; if it has, reset and move on
			   //How to check whether page is in use? what to do if dirty? 
			   if(!invPageTable.get(key).used)
				   found = true;
			   else
				   invPageTable.get(key).used = false;
			   
			   if(!clockItr.hasNext()){
				 //Hasn't found a page; Restart search from beginning
				   clockItr = invPageTable.keySet().iterator();
				   clockHand = 0;
			   }
	  }
	   
	   return key;
   }
   
   //routine to clean up all the reference to the given page:
   public static void removeReferencesToPage(int pid, int vpn){
	   String key = createKey(pid, vpn);
	   tmutex.P();
	   if(invPageTable.containsKey(key)){
		   int ppn = invPageTable.get(key).ppn;
		   invPageTable.remove(key);
		   returnPage(ppn);
		   pagesInUse.remove(key);
	   }
	   tmutex.V();

	   swapPin.P();
	   if(pagesInSwap.containsKey(key)){
		   	int offset = pagesInSwap.get(key);
	   		pagesInSwap.remove(key);
	   		freePagesInSwap.add(offset);
	   }
	   swapPin.V();
	  
	   
   }
   
   public static int getFreePage(){
   	lmutex.P();
   	int freePage = -1;
   	if(getFreeMemorySize() < 0){
		try {
			swapPageOut();
		} catch (IOException e) {
			Lib.debug(dbgVM, "Could not get free memory, exception in swap");
		}
   	}
   		
   	freePage = UserKernel.getFreePage();
   	lmutex.V();
   	return freePage;
   }
   
    // dummy variables to make javac smarter
    private static VMProcess dummy1 = null;

    private static final char dbgVM = 'v';
    //Group 7
    private static HashMap<String,TranslationEntry> invPageTable;
    private static Semaphore tmutex;
    private static Semaphore pagePin;
    private static Semaphore swapPin; 
    private static OpenFile swapFile;
    private static final String swapFileName = "swapmeinswapmeout";
    private static HashMap<String, Integer> pinnedPages; //group 7 - stores the map of pages that are in use
    private static HashMap<String, Integer> pagesInSwap; // group 7 - stores pages in swap file
    private static HashMap<String, TranslationEntry> pagesInUse; // stores all pages in use
    private static SynchList freePagesInSwap;  // list of free pages in swap
    private static final char keySeparator = ':';
    private static int clockHand;
}
